On the Secret Distributions in Module Learning With Errors

Abstract: The Module Learning With Errors (M-LWE) problem is a core assumption of lattice-based cryptography, and it underlies the security of the future post-quantum cryptography standards Kyber and Dilithium selected by NIST. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (uniform secret modulo q) and practical schemes (small bounded secret). In this talk, we narrow this gap by presenting three results focused on the secret distribution. We show that both search and decision M-LWE remain hard when the secret distribution is uniform over small bounded secret, provided that the rank is larger by a log(q) factor. We then show the hardness of search M-LWE for more general secret distributions carrying sufficient entropy.

This talk is based on the published papers "On the Hardness of Module Learning With Errors with Short Distributions" (Journal of Cryptology 2023) and "Entropic Hardness of Module-LWE from Module-NTRU" (Indocrypt 2022) which are joint works with Katharina Boudgoust, Adeline Roux-Langlois and Weiqiang Wen.

cryptography and securityMathematics

Audience: researchers in the discipline

Florida Atlantic University Crypto Café

Series comments: A seminar series of the FAU crypto group in the mathematics department. We welcome speakers, both online or in person, to join us and discuss their research or job-related opportunities. Beach lovers - come and believe!